package C.栈;

import java.util.Stack;

public class _20_有效的括号 {
    /**
     *自解：用递归====太麻烦了 因为要判断具体是那个括号 前指针移动到后面的话 都是结束括号了
     * @param s
     * @return
     */

    int front =0;
    char[] chars;
    public boolean isValid(String s) {
        chars = s.toCharArray();
        int back = chars.length-1;

        return judge(back);

    }
    public boolean judge(int back){

        if (back == 0){
            return true;
        }

        if (!judge(back-1)){
            return false;
        }
        switch (chars[front]){
            case '{':
                if (chars[back] != '}'){
                    return false;
                }
                break;

            case '[':
                if (chars[back] != ']'){
                    return false;
                }
                break;
            case '(':
                if (chars[back] != ')'){
                    return false;
                }
                break;
        }

        front++;

        return true;
    }

    /**
     * 自解：用栈---优化 如果长度为奇数 直接返回
     */

    public boolean isValid1(String s) {
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();

        for (char char_com:chars){
            //栈空判断
            if (stack.empty()){
                stack.push(char_com);
                continue;
            }

            if (char_com =='(' ||char_com =='['||char_com =='{'){
                stack.push(char_com);
                continue;
            }else if (char_com==' '){
                continue;
            }else {
                switch (char_com){
                    case ')':
                        if (stack.peek() == '('){
                            stack.pop();
                            break;
                        }else {
                            return false;
                        }
                    case ']':
                        if (stack.peek() == '['){
                            stack.pop();
                            break;
                        }else {
                            return false;
                        }
                    case '}':
                        if (stack.peek() == '{'){
                            stack.pop();
                            break;
                        }else {
                            return false;
                        }

                }
                continue;
            }

        }
        if (stack.empty()){
            return true;
        }else {
            return false;
        }


    }



}
